package com.fanshuai.algorithms.binarysearch;

/**
 * 二分搜索  用于有序列表查找
 */
public class BinarySearch {

    /**
     * 精确搜索，[left,right]闭区间
     * @param a
     * @param target
     * @return
     */
    public static int binarySearch(int[] a, int target) {
        int left = 0;
        int right = a.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == a[mid]) {
                return mid;
            } else if (target < a[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }

    /**
     * 二分搜索，有重复元素时，返回最左边的索引 [left,right)左闭右开
     * @param a
     * @param target
     * @return
     */
    public static int leftBound(int[] a, int target) {
        int left = 0;
        int right = a.length;

        while (left < right) {
            int mid = (left + right) / 2;
            if (target == a[mid]) {
                right = mid;
            } else if (target < a[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return a[left] == target ? left : -1;
    }

    /**
     * 二分搜索，有重复元素时，返回最左边的索引 [left,right]闭区间
     * @param a
     * @param target
     * @return
     */
    public static int leftBound2(int[] a, int target) {
        int left = 0;
        int right = a.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == a[mid]) {
                right = mid - 1;
            } else if (target < a[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return a[left] == target ? left : -1;
    }

    /**
     * 二分搜索，有重复元素时，返回最右边的索引 [left,right)左闭右开
     * @param a
     * @param target
     * @return
     */
    public static int rightBound(int[] a, int target) {
        int left = 0;
        int right = a.length;

        while (left < right) {
            int mid = (left + right) / 2;
            if (target == a[mid]) {
                left = mid + 1;
            } else if (target < a[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return a[left - 1] == target ? left - 1 : -1;
    }

    /**
     * 二分搜索，有重复元素时，返回最右边的索引 [left,right]闭区间
     * @param a
     * @param target
     * @return
     */
    public static int rightBound2(int[] a, int target) {
        int left = 0;
        int right = a.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == a[mid]) {
                left = mid + 1;
            } else if (target < a[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return a[left - 1] == target ? left - 1 : -1;
    }

    /**
     * 峡谷搜索 a和b有相同数量元素，a单调递增，b单调递减。
     * 设max(a,b)={max(a[i], b[i])}，则max(a,b)先单调递减，后单调递增（极端情况下，max(a,b）单调递减或单调递增）
     * 可以用二分搜索求max(a,b)最小值
     * @param a
     * @param b
     * @return
     */
    public static int findMin(int[] a, int[] b) {
        if (a.length != b.length) {
            return -1;
        }

        int left = 0, right = a.length - 1;
        int min = Integer.MAX_VALUE;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (a[mid] < b[mid]) {
                left = mid + 1;
                min = a[mid];
            } else {
                right = mid - 1;
                min = b[mid];
            }
        }

        return min;
    }

    public static void main(String[] args) {
        int[] a = {1, 3, 4, 5, 6, 6, 6, 7, 7, 8, 12, 12, 13, 14, 14, 25};
        System.out.println(binarySearch(a, 6));
        System.out.println(leftBound(a, 6));
        System.out.println(leftBound2(a, 6));
        System.out.println(rightBound(a, 6));
        System.out.println(rightBound2(a, 6));

        System.out.println("\n\n\n");
        System.out.println(binarySearch(a, 9));
        System.out.println(leftBound(a, 9));
        System.out.println(leftBound2(a, 9));
        System.out.println(rightBound(a, 9));
        System.out.println(rightBound2(a, 9));

        int[] a1 = {1, 2, 3, 4, 5, 7, 9};
        int[] b1 = {9, 7, 5, 4, 3, 2, 1};

        int[] a2 = {1, 2, 3, 4, 5, 7, 9};
        int[] b2 = {3, 2, 1, 0, 0, 0, 0};

        int[] a3 = {1, 2, 3, 4, 5, 7, 9};
        int[] b3 = {20, 18, 15, 14, 13, 6, 5};

        System.out.println("\n\n\n");
        System.out.println(findMin(a1, b1));
        System.out.println(findMin(a2, b2));
        System.out.println(findMin(a3, b3));
    }
}
